// ------------------------------ 双向链表 --------------------------------------

class Node2 {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  // 向尾部添加一个元素
  append(element) {
    let node = new Node2(element);
    // 定义最后一个元素
    let currentNode = this.tail;
    // 是空链表时，添加的元素 就是第一个元素
    if (currentNode === null) {
      this.head = node;
      this.tail = node;
    } else {
     // 不是的话 直接添加在最后一个元素即可 
     currentNode.next = node;
     // 当前添加的node prev为上一个的最后一个
     node.prev = currentNode;
     // 重新设置最后一个元素
     this.tail = node;
    }
    // 长度+1
    this.length++;
  };

  insert(position, element) {
    if (position >= 0 && position <= this.length) {
      let node = new Node2(element);
      let currentNode = this.head;
      let prevNode = null;
      let index = 0;
      // 当插入的元素在第一个位置时
      if (position === 0) {
        // 如果此时是个空链表，插入的就是第一个元素
        if (!this.head) {
          this.head = node;
          this.tail = node;
        } else {
          // 如果不是空链表，插入到第一个，更新head为node
          node.next = currentNode;
          currentNode.prev = node;
          this.head = node;
        }
      } else if (position === this.length) {
        // 插入到最后一个
        currentNode = this.tail;
        currentNode.next = node;
        node.prev = currentNode;
        this.tail = node;
      } else {
        while(index < position) {
          prevNode = currentNode;
          currentNode = currentNode.next;
          index++;
        }
        prevNode.next = node;
        node.next = currentNode;

        currentNode.prev = node;
        node.prev = prevNode;
      }
      this.length++;
      return true;
    } else {
      return false;
    }
  }

  remove(element) {
    const index = this.indexOf(element);
    this.removeAt(index);
  }

  removeAt(position) {
    if (position > -1 && position < this.length) {
      let currentNode = this.head;
      let prevNode = null;
      let index = 0;
      if (position === 0) {
        this.head = currentNode.next;
        // 如果当前只有一个元素，移除后就没了，需要更新tail
        if (this.length === 1) {
          this.tail = null;
        } else {
          // 否则把第一个元素的prev设置为null
          this.head.prev = null;
        }
      } else if (position === this.length -1) {
        // 移除最后一个元素
        currentNode = this.tail;
        this.tail = currentNode.prev;
        this.tail.next = null;
      } else {
        while(index < position) {
          prevNode = currentNode;
          currentNode = currentNode.next;
          index++;
        }
        // 找到要移除的位置
        prevNode.next = currentNode.next;
        currentNode.next.prev = prevNode;
      }
      this.length--;
      return currentNode.element
    } else {
      return false;
    }
  }

  indexOf(element) {
    let currentNode = this.head;
    let index = 0;
    while(currentNode) {
      if (currentNode.element === element) {
        return index;
      }
      currentNode = currentNode.next;
      index++;
    }
    return -1;
  }

  toString() {
    let currentNode = this.head;
    let string = '';
    while (currentNode) {
      string += ',' + currentNode.element;
      currentNode = currentNode.next;
    }
    console.log(string.slice(1));
    return string.slice(1);
  };
}

const doublyLink = new DoublyLinkedList();

doublyLink.append(2);
doublyLink.insert(0, 3);
doublyLink.insert(1, 4)
doublyLink.toString();
doublyLink.removeAt(1);
doublyLink.toString();